LZ-Kodierung

LZ-Kodierung

 

[Abk. für Lempel-Ziv-Kodierung], eine Reihe von verlustfreien Kompressionsverfahren (Komprimierung), die auf einem 1977 von Abraham Lempel und Jakob Ziv entwickelten Algorithmus basieren. Der erste, »LZ77« genannte Algorithmus wird zum Komprimieren von Text, beispielsweise mit Programmen wie PKZIP (Windows), StuffIt (Mac OS) oder Compress (Unix) verwendet. Die Komprimierung beruht darauf, dass identische Textsequenzen nicht mehrfach gespeichert werden, sondern ein Bezug zum ersten Auftreten hergestellt wird. Dabei wird angegeben, um wie viele Zeichen zurückgegangen werden muss und wie lang die zu wiederholende Sequenz ist.

 

Eine modifizierte Form dieses Algorithmus, der 1978 vorgestellte »LZ78«, legt eine Tabelle mit häufig vorkommenden Zeichensequenzen an, sodass anstelle einer solchen Zeichenfolge im Text nur der entsprechende Code aus der Tabelle eingefügt werden muss, der natürlich kürzer ist als die Zeichenfolge selbst.

 

1984 überarbeitete Terry A. Welch den LZ78 und entwickelte eine Variante, die die Firma Unisys, für die Welch arbeitete, patentieren ließ. Dieser Algorithmus ist unter der Bezeichnung LZW-Algorithmus (Abk. für Lempel-Ziv-Welch-Algorithmus) bekannt; er wird von all diesen Verfahren am häufigsten verwendet. Auch LZW ist ein tabellengesteuertes Verfahren. Basis ist eine vorgegebene Tabelle mit 256 Einträgen, die im Lauf des Kodierungsvorgangs nach den Erfordernissen der zu komprimierenden Datei erweitert wird. Sobald eine in der Tabelle vorhandene Symbolsequenz auftaucht, kann an ihrer Stelle der Tabellenindex abgespeichert werden.

 

Der LZW-Algorithmus wird z. B. bei der Datenkompression bei Modems, in GIF- und TIFF-Dateien (GIF, TIFF) sowie beim Komprimierungsprogramm LHA verwendet.